//Design a data structure that supports adding new words and finding if a string
// matches any previously added string. 
//
// Implement the WordDictionary class: 
//
// 
// WordDictionary() Initializes the object. 
// void addWord(word) Adds word to the data structure, it can be matched later. 
//
// bool search(word) Returns true if there is any string in the data structure t
//hat matches word or false otherwise. word may contain dots '.' where dots can be
// matched with any letter. 
// 
//
// 
// Example: 
//
// 
//Input
//["WordDictionary","addWord","addWord","addWord","search","search","search","se
//arch"]
//[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
//Output
//[null,null,null,null,false,true,true,true]
//
//Explanation
//WordDictionary wordDictionary = new WordDictionary();
//wordDictionary.addWord("bad");
//wordDictionary.addWord("dad");
//wordDictionary.addWord("mad");
//wordDictionary.search("pad"); // return False
//wordDictionary.search("bad"); // return True
//wordDictionary.search(".ad"); // return True
//wordDictionary.search("b.."); // return True
// 
//
// 
// Constraints: 
//
// 
// 1 <= word.length <= 500 
// word in addWord consists lower-case English letters. 
// word in search consist of '.' or lower-case English letters. 
// At most 50000 calls will be made to addWord and search. 
// 
// Related Topics 深度优先搜索 设计 字典树 字符串 
// 👍 275 👎 0


package leetcode.editor.cn;

//Java：Design Add and Search Words Data Structure
class P211DesignAddAndSearchWordsDataStructure {
    public static void main(String[] args) {
        WordDictionary solution = new P211DesignAddAndSearchWordsDataStructure().new WordDictionary();
        // TO TEST
        solution.addWord("bad");
        solution.addWord("dad");
        solution.addWord("mad");
        solution.search("pad");
        solution.search("bad");
        solution.search(".ad");
        solution.search("b..");

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class WordDictionary {
        int R = 256;
        Node alph;

        /**
         * Initialize your data structure here.
         */
        public WordDictionary() {
            alph = new Node();

        }

        public void addWord(String word) {
            char[] chars = word.toCharArray();
            Node[] child = alph.getChild();
            Node[] preChild = child;
            Node node = null;
            for (char c : chars) {
                node = preChild[(int) c];
                if (node == null) {
                    node = new Node();
                }
                preChild[(int) c] = node;
                preChild = node.getChild();
            }
            node.setC(word);
        }

        public boolean search(String word) {
            return search(word, 0, alph);
        }

        private boolean search(String word, int depth, Node child) {
            if (depth == word.length()) {
                return child.getC() != null;
            }
            char c = word.charAt(depth);
            if (c == '.') {
                Node[] sim = child.getChild();
                Boolean flag = false;
                for (Node node : sim) {
                    if (node == null) {
                        continue;
                    }
                    flag = flag | search(word, depth + 1, node);
                }
                return flag;
            } else if (child.getChild()[c] != null) {
                return search(word, depth + 1, child.getChild()[c]);
            } else {
                return false;
            }
        }

        class Node<Value> {
            Node[] child = new Node[256];
            Value c;

            public Node[] getChild() {
                return child;
            }

            public void setChild(Node[] child) {
                this.child = child;
            }

            public Value getC() {
                return c;
            }

            public void setC(Value c) {
                this.c = c;
            }
        }
    }

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */
//leetcode submit region end(Prohibit modification and deletion)

}